1. Field of the Invention
The present invention relates to a content addressable memory circuit used in a content addressable memory system, and to the structure of a content addressable memory cell used in such a content addressable memory circuit.
2. Description of the Background Art
In systems utilizing microprocessors, a memory structure of at least two levels is generally used including an external storage unit of low speed and large storage capacity such as a magnetic disk, and a storage unit using semiconductor devices having a speed higher than that of a disk storage unit. A memory device which is directly accessed by a microprocessor is generally formed of a semiconductor device.
A memory device using a semiconductor device includes a dynamic type semiconductor memory device (DRAM) carrying out dynamic operation, and a static type semiconductor memory device (SRAM) carrying out static operation. A DRAM requires a signal line to be precharged to a predetermined potential for this dynamic operation, and is generally slower than a SRAM. In systems using a processor such as a microprocessor, a DRAM circuit operating at a relatively low speed and having a large storage capacity, and a SRAM circuit operating at a high speed but having only a small storage capacity are used so as not to degrade the high speed performance of the processor.
FIG. 9 shows a conventional structure of a data processing system using a processor. Referring to FIG. 9, the data processing system includes a processor 31 formed of, for example, a microprocessor, a cache memory 30 operating at a high speed, and a DRAM circuit 34 serving as the main memory of a large storage capacity. The cache memory 30 includes a high speed operating SRAM circuit 33 of a small storage capacity, and a CAM circuit 32 for storing the tag address of the data stored in the SRAM circuit 33.
The data required by the processor 31 is generally stored in the DRAM circuit 34 of a large storage capacity. Regarding the data stored in this DRAM circuit 34, the data used frequently by the processor 31 is stored in the SRAM circuit 33 in the cache memory 30. The processor 31 normally accesses the SRAM circuit 33 in the cache memory 31. The SRAM circuit 33 operates at a high speed. Therefore, the high speed operating performance of the processor 31 is not degraded and data processing can be executed at high speed in the case where the processor 31 frequently uses the data stored in the SRAM circuit 33. When the processor 31 uses data not stored in the SRAM circuit 33, the processor 31 accesses the DRAM circuit 34.
By establishing a hierarchical structure of a memory with a high speed operating cache memory 30 and a DRAM circuit 34 of large storage capacity but of low speed, the processor 31 can behave as if a high speed memory device of large storage capacity is used, since the frequently used data is stored in the cache memory 30 that operates at high speed. Therefore, the data processing system can operate at a high speed.
A CAM circuit 32 is provided in the cache memory 30 for making determination on whether the data required by the processor 31 exists or not in the SRAM circuit 33. The CAM circuit 32 stores the tag addresses of the data stored in the SRAM circuit 33. In general, a data block from the DRAM circuit 34 serving as a main storage is transferred to the SRAM circuit 33 to be stored therein. The tag address stored in the CAM circuit 32 is the address section common to each data in that data block. The SRAM circuit 33 does not store fixed data. According to the requirements of the processor 31, the data area on the DRAM circuit 34 stored by the SRAM circuit 33 varies. However, localization exists in the memory region accessed by the processor 31 in certain data processing. In other words, when a certain data is accessed, there is a high possibility that data of a succeeding address or data proximate thereto will be accessed. This means that the data fetched from the DRAM circuit 34 serving as the main memory to be stored in the SRAM circuit 33 of the cache memory 30 according to a request from the processor 31 may be accessed by the processor 31 thereafter for some time period in a high probability. If the data of the DRAM circuit 34 is stored into the SRAM circuit 33 of the cache memory 30, the high speed operation of this SRAM circuit 33 is fully exhibited to realize memory access of the processor 31 with no waiting (no wait). The processor 31 will not have its processing operation delayed by the memory access time.
The CAM circuit 32 receives the tag address section of an address signal ADD provided from the processor 31 to the address bus 36 to make comparison with a tag address stored therein. When the tag address supplied on the address bus 36 matches the tag address stored in the CAM circuit 32, the CAM circuit 32 generates a signal CH on the signal line 37. The cache memory is said to be "hit" if there is data needed by the processor 31 in the cache memory 30. The signal CH is activated when the cache memory is hit. The processor 31 responds to the cache hit signal CH on the signal line 37 to access the SRAM circuit 33 or the DRAM circuit 34.
As described above, the CAM circuit 32 functions to compare a provided tag address with a tag address stored therein to generate a signal indicating the comparison result. The CAM circuit 32 can also write and read an externally applied data such as a typical memory circuit. A memory circuit called a content addressable memory is used in the CAM circuit 32.
FIG. 10 shows the functional structure of a CAM circuit. Referring to FIG. 10, the CAM circuit 32 includes a storage region 102 for storing a tag address, and an input circuit 101 for entering a data to be compared (a tag address). In FIG. 10, the storage region 102 is shown including 256 address regions A0-A255. The tag address of the data stored in the SRAM circuit is stored in each of the address regions of A0-A255. Each of address regions A0-A255 of the storage region 102 compares the input data D0-D7 from the input circuit 101 with the tag address stored therein to transfer a signal indicating the comparison results to a matching line 104. A matching line 104 is provided corresponding to each address region.
The CAM circuit further includes a match detection circuit 103 responsive to a signal applied to the matching line 104 for detecting whether the input data D0-D7 provided from the input circuit 101 matches any of the tag addresses stored in the storage region 102. When a tag address stored in any of the address regions A0-A255 of the storage region 102 matches the tag addresses D0-D7 provided from the input circuit 101, the corresponding matching line 104 indicates a matching state. The match detection circuit 103 responds to a match indicating signal on the matching line 104 to generate a cache hit signal CH.
As described above, access to the SRAM circuit 33 is carried out at the time of cache hit in which the cache memory is hit. At the time of cache miss when the cache memory is not hit, access to the DRAM circuit is carried out. At this time, the data block including the accessed data is transferred to the SRAM circuit 33 parallel to the access to the DRAM circuit. The data transfer operation from the DRAM circuit to the SRAM circuit at the time of a cache miss is schematically shown in FIG. 11.
Referring to FIG. 11, a case is considered where the data requested by the processor 31 is included in a data block DB1 in a region in the DRAM circuit 34. The data block DB1 is transferred to the SRAM circuit 33. The address common to the words included in the data block DB1 is the tag address.
The data DB2 stored in a region A in the SRAM circuit 33 is transferred back to a corresponding region A2' in the DRAM circuit 34 (in the case of a copy back operation). The least recently accessed region is selected (LRU logic) as the region A in the SRAM circuit 33. Therefore, at the time of a cache miss, a new data block DB1 is transferred from the DRAM circuit 34 to the SRAM circuit 33, and rewriting of the tag address is executed in the CAM circuit 32. The CAM circuit 32 has a data rewriting function, i.e. data input/output function for executing the rewrite of a tag address in the CAM circuit 32.
FIG. 12 shows an example of a specific structure of a CAM circuit. Referring to FIG. 12, a CAM circuit includes a plurality of CAM cells 41 arranged in a matrix of rows and columns, an address decoder circuit 2 for decoding an address signal ADD provided via an address bus 8 to select CAM cells of one row, and a read/write circuit 3 for generating and transmitting to bit lines 6a and 6b an internal write data from data D provided via a data bus 9, and for generating an external read out data from the internal read out data transmitted from bit lines 6a and 6b at the time of data read out.
In FIG. 12, the CAM cells 41 are shown, as an example, being arranged in m rows and n columns, with reference numerals 41-11 . . . , 41-1n, . . . , 41-1m, . . . 41-mn. The address decoder circuit 2 includes m word lines 13-1 to 13-m to decode the address signal ADD provided via the address bus 8 to set one of the word lines to a selected state. The read/write circuit 3 carries out data input/output via the data bus 9, with a write data D and a read out data Q indicated together as DQ.
The CAM circuit further includes matching lines 11-1 to 11-m arranged corresponding to the word lines 13, and an OR circuit 10 to receive signals of matching lines 11-1 to 11-m for carrying out a logical sum operation. A cache hit signal CH is provided from the OR circuit 10 via a signal line 7.
One row of CAM cells are connected to each of matching lines 11-1 to 11-m. Each of matching lines 11-1 to 11-m is connected to receive a power potential 14 to be precharged to an H level (logical high) of the operating power potential Vcc level.
Bit lines 6a and 6b transmit signals complementary to each other. A signal having the same logic level of the input data is transmitted to the bit line 6a, and a signal having a logic opposite to the input data is transmitted to the bit line 6b. One column of CAM cells are connected to each pair of bit lines 6a and 6b.
Each of CAM cells 41-11 to 41-mn includes the function to compare the data provided to associated bit line 6a and 6b with a stored data to drive the associated matching line 11 according to the comparison results, in addition to the data storage function. The operation of the CAM circuit shown in FIG. 12 will be described briefly.
At the time of writing or reading data to or from a CAM cell, the address decoder circuit 2 decodes an address signal ADD provided via the address bus 8 to select one word line 13 (one of word lines 13-1 to 13-n). One row of CAM cells connected to the selected word line 13 are connected to the related corresponding bit lines 6a and 6b. At the time of data writing, an input from the read/write circuit 3 is transmitted to bit lines 6a and 6b. The selected CAM cell 41 stores the data on the corresponding bit lines 6a and 6b. At the time of data reading, the CAM cell 41 provides the stored data to the corresponding bit lines 6a and 6b. The data output to bit lines 6a and 6b are provided to the data bus 9 via the read/write circuit 3.
The match detecting operation will be described hereinafter. In this case, the address decoder circuit 2 is at an inactive state, and the decoding operation is not carried out. The read/write circuit 3 generates an internal data from the data provided from the data bus 9 to transmit the same to bit lines 6a and 6b. Here, one word line corresponds to one word. The matching line 11 is precharged to a H level. A data bit is transmitted to each bit line pair from the read/write circuit 3. Each CAM cell 41 compares the data provided on the corresponding bit lines 6a and 6b with the data already stored therein. If the data on the corresponding bit lines 6a and 6b match the stored data, the CAM cell 41 holds the matching line 11 at a floating state. When the data of the corresponding bit lines 6a and 6b do not match the stored data, the CAM cell 41 has the corresponding matching line 11 discharged to ground potential. Therefore, in the case the input data provided from the read/write circuit 3 matches the data bit stored respectively in one row of CAM cells, the potential of the matching line 11 attains a H level of the power potential. If there is a mismatch in any of the bits, the corresponding matching line 11 is discharged to ground potential to attain a L level.
The OR circuit 10 takes the logical sum of the signals on matching lines 11-1 to 11-m. Therefore, when one matching line 11 attains a H level indicating a matching state, a cache hit signal CH of a H level indicating an active state is sent to the signal line 7 from the OR circuit 10.
As mentioned above, one row of memory cells connected to one word line 13 corresponds to one word, whereby the read/write circuit 3 carries input/output of data in the unit of a word. A signal indicating the comparison result between each bit of a word and the input data is transmitted to the matching line 11. The matching line 11 has a potential of H level only in the case of matching. By using the CAM circuit of FIG. 12, a signal indicating the match/mismatch of a tag address can be provided from the OR circuit 10 at a high speed.
FIG. 13 shows a specific structure of a CAM cell. Referring to FIG. 13, a CAM cell 41 includes access transistors 23a and 23b responsive to a word line selecting signal on the word line 13 for connecting storage nodes 24a and 24b to bit lines 6a and 6b, respectively, an n channel MOS (insulating gate type field effect) transistor 23c connecting the storage node 24b to ground potential 22 according to the data stored in the storage node 24a, an n channel MOS transistor 23d connecting the storage node 24a to ground potential 22 according to the data stored in the storage node 24b, and pull-up resistor elements 21a and 21b for coupling storage nodes 24a and 24b respectively to power potential 14. Transistors 23c and 23d implement a flipflop type latch circuit. By this latch circuit, the data transmitted to bit lines 6a and 6b are stored in storage nodes 24a and 24b.
The CAM cell 41 further includes an n channel MOS transistor 23f for receiving at its gate a signal on the bit line 6a, an n channel MOS transistor 23e responsive to the data on the bit line 6b for conducting to transmit ground potential 22, an n channel MOS transistor 23h coupling selectively the transistor 23f to the matching line 11 according to the data stored in the storage node 24b, and an n channel MOS transistor 23g for selectively transmitting to the matching line 11 ground potential 22 transmitted by the transistor 23e, according to the stored data in the storage node 24a. Transistors 23e, 23f, 23g and 23h carry out the determination of match/mismatch between stored data and data on bit lines 6a and 6b to drive the matching line 11 according to the determination result.
The matching line 11 has the comparison/driving portion of each CAM cell 41 coupled in a wired-AND fashion. In the following description, the horizontal direction in FIG. 13 is referred to as the bit direction, and the vertical direction is referred to as the word direction. The operation of the CAM cell shown in FIG. 13 will be described hereinafter.
(1) Data storing operation
The operation of storing data into a CAM cell in a CAM circuit is similar to that of a memory circuit such as DRAMs and SRAMs. More specifically, in the case of storing data into the CAM cell 41, write data (data to be stored) is transmitted to bit lines 6a and 6b, and a word line selecting signal is transmitted to the word line 13. When the signal potential of the word line 13 attains a H level, access transistors 23a and 23b are turned on, whereby storage nodes 24a and 24b are connected to bit lines 6a and 6b, respectively.
Now, the case is considered where the data of bit lines 6a and 6b are "H" and "L", respectively. In this case, the potential of the storage node 24a attains a H level, and the potential of the storage node 24b attains a L level. Because the potential of the storage node 24b is at a L level, transistor 23d is turned off. The transistor 23c is turned on because of a H level potential of the storage node 24a. Accordingly, the storage node 24a is pulled up via the resistor element 21a to attain a H level, whereas the storage node 24b is discharged to ground potential 22 via the transistor 23c to maintain the L level. Thus, the data of "H" and "L" transmitted to bit lines 6a and 6b are stored in storage nodes 24a and 24b, respectively.
In this state, the transmitted data on the bit lines 6a and 6b match the stored data in storage nodes 24a and 24b. The matching line 11 is held at a floating state by transistors 23e, 23f, 23g and 23h.
(2) Data reading operation
The data reading operation is similar to the above described data writing operation, except that the direction of the data flow is different. More specifically, by the rise in potential of the word line 13, storage nodes 24a and 24b are connected to bit lines 6a and 6b, and the data stored in storage nodes 24a and 24b are transmitted to bit lines 6a and 6b, respectively. The data transmitted to bit lines 6a and 6b are transmitted to read/write circuit 3 to be detected/amplified and provided therefrom.
(3) Data comparison operation
It is assumed that the H level potential supplied from the power potential 4 corresponds to logic value "1" and the L potential supplied from ground potential 22 corresponds to logic value "0". It is assumed that a signal line provides a logic value of 0 when that signal line is connected to both power potential 14 and ground potential 22. Because the matching line 11 is connected to power potential 14, as shown in FIG. 12, the signal on that matching line 11 is normally logic value 1.
Consider a case where data 1 is stored in the CAM cell 41. More specifically, storage node 24a stores 1 and storage 24b stores 0 in FIG. 13. The external data to be compared are transmitted via the read/write circuit 3. When the data to be compared is 1, bit lines 6a and 6b become 1 and 0, respectively. At this time, the transistor 23f is turned on, and transistor 23e is turned off. Transistors 23g and 23h having their gates connected to storage nodes 24a and 24b, respectively, are turned off and on, respectively. Under this state, the matching line 11 maintains 1 because ground potential 22 is not connected thereto.
When the CAM cell 41 stores data 0 and the external data to be compared is 0, transistors 23g and 23f are similarly turned off, and transistors 23e and 23h are turned on, so that the matching line 11 is not coupled to ground potential 22.
Thus, when the data stored in the CAM cells 41 along the bit direction are equal to the bit values of the external data to be compared, the matching line 11 takes a logic value of 1 because it is not coupled to ground potential 22, as described above. In other words, when there is a data in the CAM circuit that matches the external data to be compared, the logic value of the matching line 11 is 1.
Consider a case where data 0 is stored in CAM cell 41, and the external data to be compared is 1. Storage nodes 24a and 24b are 0 and 1, respectively, and bit lines 6a and 6b are 1 and 0, respectively. At this state, transistors 23f and 23h are both turned on, and transistors 23e and 23g are turned off. The matching line 11 is coupled to ground potential 22 via transistors 23h and 23f.
Therefore, when there is at least one bit unequal data between the data to be compared and the stored data in all the CAM cells of one row arranged in the bit direction, the matching line 11 is connected to ground potential 22, so that the matching line 11 takes a logic value of 0 in the CAM cell 41.
As a result of comparing data stored in an arbitrary word (formed of CAM cells connected to one word line) with external data, the matching line 11 corresponding to that word takes a logic value of 1 when the comparison result is equal, and a logic value of 0 when not equal. Different data are stored in respective words in the CAM circuit. The logic values of the matching lines 11 can provide either a state where "only one matching line is 1", or where "all the matching lines are 0". The matching lines will not take a logic value of 1 for more than 1 word, because the contents of the stored word differs for each row.
If at least one matching line 11 indicates a logic value 1 in the CAM circuit 32, the cache hit signal CH provided to the signal line 7 takes a logic value of 1 by the OR circuit 10 shown in FIG. 12. When all the matching lines 11 take a logic value of 0, i.e. when the data to be used by the processor 31 does not exist in the cache memory 30, the cache hit signal CH of the signal line 7 takes a logic value of 0. The processor 31 recognizes whether the required data exist or not in the cache memory 30 according to the cache hit signal CH.
In the above description, a CAM circuit is used in the cache memory. The CAM circuit is also used in high speed conversion buffers called TLB (Translation Look-Aside Buffer) circuits. TLB circuit will be described briefly hereinafter. In processors such as of CPUs, various storage management systems are used. One of such a storage management system is a virtual storage system. In this virtual storage system, the program is created for a logical storage unit that is individually separated from the main storage which is the physical storage unit. The relating between the logical storage unit and the physical main storage unit is carried out at the time of program execution. The logical storage unit is called a virtual storage or virtual space, and the address on the virtual storage is called a virtual address. The address on the main storage unit is called a real address. The size of the virtual storage is not dependent on the size of the main storage.
A virtual storage normally has a structure divided into storage units called a page or a segment with a size of 2 to 64K bytes. The storage unit for physical storage of the virtual storage used by the program includes a main storage and a secondary storage of large capacity such as a magnetic disk. Data portions (pages or segments) that cannot be stored in the main storage is stored in the secondary storage. The page (segment) in the secondary storage is transferred to the main storage when required at the time of program execution. It is necessary to convert the virtual address into a real address at this time. The TLB circuit is used to carry out this conversion operation speedily. The operation of a TLB circuit used in address conversion in a segmentation system will be described briefly hereinafter.
FIG. 14 shows the functional structure for carrying out address conversion from a virtual address to a real address according to a segmentation system. In the segmentation system, the virtual space is founded of a plurality of segments. A segment is a unit having a logically complete meaning in the program. For example, a segment is an array data or a subroutine. A virtual address is formed of a segment number SN for identifying a segment, and a relative displacement D in the segment indicating a specific instruction or data in a segment.
For converting a virtual address into a real address, a segment table 201 serving as a corresponding table of a virtual address and a real address is provided. The segment table 201 includes an entry called a segment descripter provided in correspondence with all segments. The segment descripter 210 is provided corresponding to each segment. The contents of a segment descripter includes an existence flag indicating whether a corresponding segment exists or not on the main storage, the head address (real address) on the main storage of the segment in the case of existing on the main storage, and the size of the segment. The segment table 201 is generally provided in the main storage.
Consider a case where segment number Sn and an in-segment relative displacement D are provided as the virtual address. According to segment number Sn, a corresponding segment descripter is accessed from the segment table 201. When the existence flag in the segment descripter 210 indicates that the corresponding segment exists on the main storage, the head real address of the corresponding segment can be obtained by the head address included in the segment descripter. The in-segment relative displacement D is added to the real address by an adder 215. The output of the adder 215 is the real address corresponding to the required virtual address.
Such an address conversion is carried out for each execution of an instruction. The segment table 201 is often stored in the main storage which operates at a relatively low speed. This means that operation cannot be carried out speedily if the segment table 201 in the main storage is accessed every time address conversion is required. A TLB circuit 202 is provided for solving such problem.
Referring to FIG. 15, a pair of a head virtual address (segment number) and a corresponding real address of a recently accessed segment is held in the TLB circuit 202. The address conversion in accessing a segment held in the TLB circuit 202 is carried out using the address conversion pairs stored in the TLB circuit 202. More specifically, a segment number S is supplied to the TLB circuit 202, whereby determination of match/mismatch with the virtual address (the head virtual address of the segment) stored therein is carried out. The corresponding real address R is provided if there is matching virtual address.
If the required address conversion pair does not exist in the TLB circuit 202, access is made to the segment table 201 provided in the main storage to access a corresponding segment descripter 210. By selecting a real address from the TLB circuit 202 or a real address from the segment descripter 210 included in the segment table 201 with the OR circuit 220, the head real address of the segment 203 can be obtained.
In the above-described TLB circuit, a CAM circuit is employed for making determination of a match/mismatch between the segment number included in the virtual address and the virtual address stored therein.
FIG. 16 schematically shows the structure of a TLB circuit. Referring to FIG. 16, the TLB circuit includes a CAM array 250 formed of a plurality of CAM cells storing a segment number and a corresponding real address, an address decoder 252 for selecting one row (one word) in the CAM array according to a supplied address signal, an input/output circuit 254 for carrying out data input/output with respect to one word of CAM cells selected by the address decoder 252, a retrieval circuit 256 for generating an internal retrieval data according to an externally applied retrieval data and to apply a mask process to unnecessary data bits for transmitting the same to columns in the CAM array 250, and a resolver encoder 258 for detecting the match/mismatch between the retrieval data and the stored word data in the CAM array 250, and for providing the address of the matching word in case of matching.
The TLB circuit of FIG. 16 can carry out data writing and reading with respect to a desired word via the input/output circuit 254 by the operation of the address decoder 252, similar to a random access memory.
At the time of retrieval mode (comparison operation), the retrieval data (the segment number of the virtual address) from the retrieval circuit 256 is supplied to the CAM array 250. In each word, determination of match/mismatch between the retrieval data from the retrieval circuit 256 and the stored word data is carried out. The determination result is provided to the resolver encoder 258 via the matching line. The resolver encoder 258 responds to a signal on the matching line from the CAM array 250 to provide a match signal indicating the match/mismatch and generates the address of the matching data word. The address from the resolver encoder 258 is supplied to the address decoder 252, whereby a word selecting operation is carried out to read out a corresponding real address Rn via the input/output circuit 254.
The CAM cell included in the CAM array 250 of FIG. 16 has a structure similar to that of the above-described CAM circuit, except that a function to read out the data of a matching word is further included in the resolver encoder 258.
In the case where the data to be used by the processor 31 such as a microprocessor does not exist in the cache memory 30 in a CAM circuit used in the cache memory, it is necessary to transfer the data block including the required data to the SRAM circuit from the DRAM circuit serving as the main storage. It is also necessary to rewrite the tag address stored in the CAM circuit. Which address region in the SRAM circuit should be subjected to rewrite of a data block is determined according to a certain rule. More specifically, in the case of rewriting a tag address stored in the CAM circuit, the determination of which tag address should be rewritten is carried out according to a certain rule. An LRU algorithm is known as a rule of rewriting data in a cache memory. In the LRU (least recently used) algorithm, the recently least frequently used data is discarded and a new data is rewritten. Normal processors such as microprocessors have a feature to access continuously the same address region. Therefore, data substitution by LRU algorithm is most efficient.
However, it is necessary to identify which address was least frequently used in the case the LRU algorithm is used. An history indicating how and when each data and the cache memory was accessed must be stored. Storing such a history and carrying out data rewrite according to the stored history will become a very complicated process, which is usually carried out with a software.
The data transferred from, for example, a segment table, is a segment region recently used in the TLB circuit. If a corresponding virtual address is not stored in the TLB circuit, the contents must be rewritten by a segment descripter in the segment table. This rewriting also employs the LRU algorithm. The application of a TLB circuit utilizing a CAM circuit is not limited to the segmentation method, and can be employed in other virtual storage systems such as the page system, where the data substitution is carried out also according to LRU algorithm.
A procedure flow of the LRU algorithm is shown in FIG. 17. The LRU algorithm will be described briefly hereinafter with reference to FIG. 17.
At the time of system starting, each status value j indicating the access sequence corresponding to each entry (stored contents of address) of the CAM circuit is initialized (step S2).
Upon operation of the processor, the comparison determination operation is executed (step S4). If the cache is hit, the status value j corresponding to the hit entry (access address ) is initialized, and the status value j corresponding to the remaining full entries (entries having valid data stored therein ) is incremented by 1 (step S6).
If the cache is not hit ( cache miss ) , determination is made whether all the entries of the CAM circuit store data or not (step S8). This determination can be made by checking the valid data bit provided corresponding to each entry. If all the entries in the CAM circuit store valid data, the address of the entry corresponding to the highest status value is provided. Furthermore, the highest status value of the address corresponding to this highest status value is initialized, and the status values corresponding to the remaining entries are incremented by 1 (step S12).
If data is not stored in all of the entries in the CAM circuit and there are still empty entries, the smallest address of the empty entries is provided. The status values j of the full entries are incremented by 1 (step S10) . The operations of steps S6, S12 , and S10 are repetitively executed until the termination of the system operation (step S14) .
In the case of executing the above-described operation with a software, the procedure operation must be executed by the processor 31 itself, or by a processor dedicated to cache memory control or TLB circuit management in the memory system. It will be a great load to the processor 31 if the management of the cache memory is additionally executed by the processor 31, resulting in degradation of the processing performance of that processor. If a dedicated processor is used, the structure size of the system and also the cost thereof will be increased.
There is also a problem that the processing speed will be reduced in carrying out the procedure with a software, so that the processing operation at the time of cache miss cannot be executed speedily.
An example of a content addressable memory circuit realizing the LRU algorithm in a hardware manner is disclosed in Japanese Patent Laying-Open No. 61-204896. According to this prior art, the content addressable memory circuit includes a plurality of data registers each holding a comparison standard data, a plurality of comparison circuits for comparing the stored contents of each data register with an input data, and control means for rewriting the contents of the data register by a shifting operation according to the outputs of the plurality of comparison circuits. In the prior art, the contents of all data registers upstream of the data register holding the storage content matching the input data are rewritten by the shifting operation to an upstream adjacent data register. The input data is stored in the most upstream data register.
This prior art realizes LRU algorithm by the shifting operation of cascade-connected data registers. However, the data register and the comparison circuit are provided individually, in addition to a selecting circuit for controlling the shifting operation of a data register according to the output of a plurality of comparison circuits. This means that the complexity of the device is increased. There is no disclosure of the structure of the data register, and no suggestion of using a CAM cell.